package leetcode.median;

import leetcode.base.TreeNode;

import java.util.LinkedList;
import java.util.List;

/**
 * ClassName: $95_GenerateTrees
 * Description:
 * date: 2021-11-17 22:20
 *
 * @author liyifan
 */
public class $95_GenerateTrees {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0)
            return new LinkedList<>();
        return build(1, n);
    }

    public List<TreeNode> build(int low, int high){
        List<TreeNode> res = new LinkedList<>();
        if (low > high) {
            res.add(null);
            return res;
        }
        for (int i = low;i <= high;i++) {
            List<TreeNode> leftTrees = build(low, i - 1);
            List<TreeNode> rightTrees = build(i + 1, high);
            for (TreeNode left:leftTrees) {
                for (TreeNode right:rightTrees) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    res.add(root);
                }
            }
        }
        return res;
    }
}
